import numpy as np
from copy import deepcopy
#以0代表空格
destination=[
    [1,2,3],
    [8,0,4],
    [7,6,5]
]

def search_branch(node:list,iter_g:int):
    """
    搜索当前的结点，附加初始结点到该结点的耗散值
    """
    for i in range(3):
        for j in range(3):
            if node[i][j]==0:
                break
        else:
            continue
        break
    change_index=[[i+1,j],[i-1,j],[i,j-1],[i,j+1]]
    index_valid=[[k,m] for k in range(3) for m in range(3)]
    changes=[]
    for k in change_index:
        if k not in index_valid:
            changes.append(k)
    for k in changes:
        change_index.remove(k)
    node_list=[]
    for k in change_index:
        new_node=deepcopy(node)
        new_node[k[0]][k[1]]=0
        new_node[i][j]=node[k[0]][k[1]]
        node_list.append((new_node,iter_g+1))
    return node_list

def h(node:list):
    """
    当前状态到最终状态的估价函数
    """
    iter_h=0
    for i in range(3):
        for j in range(3):
            if destination[i][j]!=node[i][j]:
                iter_h+=1
    return iter_h
def trace_back(close_list:list):
    """
    根据close_list的耗散值逆向搜索出所找到的最优路径
    """
    divide=[]
    for sss in range(close_list[-1][-1]+1):
        sub=[]
        for node in close_list:
            if node[-1]==sss:
                sub.append(node[0])
        divide.append(sub)
    divide.reverse()
    route=[destination]
    for sub in divide:
        #print(sub)
        root=route[-1]
        roots=[item[0] for item in search_branch(root,0)]
        for fd in sub:
            if fd in roots:
                route.append(fd)
                break
    route.reverse()
    return route

def main(start_state:list):
    """
    用于搜索的主循环
    """
    open_list=[(start_state,0)]
    close_list=[]
    while open_list!=[] and destination!=open_list[0][0]:
        node=open_list[0]
        open_list.remove(node)
        close_list.append(node)
        new_nodes=search_branch(node[0],node[1])
        close_lists=[k[0] for k in close_list]
        open_lists=[k[0] for k in open_list]
        for new_node in new_nodes:
            if new_node[0] in close_lists:
                for i in range(len(close_list)):
                    if new_node[0]==close_list[i][0]:
                        if new_node[1]+h(new_node[0])<close_list[i][1]+h(close_list[i][0]):
                            close_list[i]=new_node
                            break
            elif new_node[0] in open_lists:
                for i in range(len(open_list)):
                    if new_node[0]==open_list[i][0]:
                        if new_node[1]+h(new_node[0])<open_list[i][1]+h(open_list[i][0]):
                            open_list[i]=new_node
                            break
            else:
                open_list.append(new_node)
        for j in range(len(open_list)-1):#升序排序
            for i in range(len(open_list)-1-j):
                if open_list[i][1]+h(open_list[i][0])>open_list[i+1][1]+h(open_list[i+1][0]):
                    open_list[i],open_list[i+1]=open_list[i+1],open_list[i]
    return close_list

if __name__ == '__main__':
    start_state=[
        [2,4,8],
        [1,3,5],
        [7,0,6]
    ]
    #print(search_branch(start_state,0))
    close_list=main(start_state)
    route=trace_back(close_list)
    for num,node in enumerate(route):
        print(f'Step {num+1}:\n',np.array(node))